package huawei_nowcoder;

import org.w3c.dom.Node;

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

/**
 * @Description: 迷宫问题
 * @Date: 2020/4/26
 * @Author: 许群星
 */
public class MazeQuestion {
    static int n, m;
    static int[][] grid;

    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);
        while (sc.hasNext()) {
            //得到数据
            n = sc.nextInt();
            m = sc.nextInt();
            grid = new int[n][m];
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < m; j++) {
                    grid[i][j] = sc.nextInt();
                }
            }
            //处理
            getShortestPath(0, 0);
            sout(0, 0);
        }
    }

    //找迷宫最短路径   左上角到右下角
    private static void getShortestPath(int i, int j) {
        if (i == n - 1 && j == m - 1) {
            return;
        }
        //向右
        if (i + 1 < n && grid[i + 1][j] != 1) {
            getShortestPath(i + 1, j);
        }
        //向下
        if (j + 1 < m && grid[i][j + 1] != 1) {
            getShortestPath(i, j + 1);
        }
        //不能向下也不能向右 回溯的时候把路封上
        if (i + 1 == n && grid[i][j + 1] == 1) {
            grid[i][j] = 1;
        }
        //不能向下页不能向右 也不再终点
        if (i + 1 != n && j + 1 != m) {
            if (grid[i + 1][j] == 1 && grid[i][j + 1] == 1) {
                grid[i][j] = 1;
            }
        }
    }

    //打印对应的节点
    private static void sout(int i, int j) {
        if (i == n - 1 && j == m - 1) {
            System.out.println("(" + i + "," + j + ")");
        }
        //向下
        if (i + 1 < n && grid[i + 1][j] != 1) {
            System.out.println("(" + i + "," + j + ")");
            sout(i + 1, j);
        }
        //向右
        if (j + 1 < m && grid[i][j+1] != 1) {
            System.out.println("(" + i + "," + j + ")");
            sout(i, j + 1);
        }
    }
}
/*
题目描述
定义一个二维数组N*M（其中2<=N<=10;2<=M<=10），如5 × 5数组下所示：
int maze[5][5] = {
    0, 1, 0, 0, 0,
    0, 1, 0, 1, 0,
    0, 0, 0, 0, 0,
    0, 1, 1, 1, 0,
    0, 0, 0, 1, 0,
};
它表示一个迷宫，其中的1表示墙壁，0表示可以走的路，只能横着走或竖着走，不能斜着走，要求编程序找出从左上角到右下角的最短路线。入口点为[0,0],既第一空格是可以走的路。
Input
一个N × M的二维数组，表示一个迷宫。数据保证有唯一解,不考虑有多解的情况，即迷宫只有一条通道。
Output
左上角到右下角的最短路径，格式如样例所示。
Sample Input
0 1 0 0 0
0 1 0 1 0
0 0 0 0 0
0 1 1 1 0
0 0 0 1 0
Sample Output
(0, 0)
(1, 0)
(2, 0)
(2, 1)
(2, 2)
(2, 3)
(2, 4)
(3, 4)
(4, 4)

输入描述:
输入两个整数，分别表示二位数组的行数，列数。再输入相应的数组，其中的1表示墙壁，0表示可以走的路。数据保证有唯一解,不考虑有多解的情况，即迷宫只有一条通道。
输出描述:
左上角到右下角的最短路径，格式如样例所示。
示例1
输入
复制
5 5
0 1 0 0 0
0 1 0 1 0
0 0 0 0 0
0 1 1 1 0
0 0 0 1 0
输出
复制
(0,0)
(1,0)
(2,0)
(2,1)
(2,2)
(2,3)
(2,4)
(3,4)
(4,4)
 */